package com.ljy.my_study.lintcode.K个最近的点;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @author James
 * @date 2018年10月11日
 */
public class TestMain {
	// 描述
	// 给定一些 points 和一个 origin，从 points 中找到 k 个离 origin
	// 最近的点。按照距离由小到大返回。如果两个点有相同距离，则按照x值来排序；若x值也相同，就再按照y值排序。
	//
	// 您在真实的面试中是否遇到过这个题？
	// 样例
	// 给出 points = [[4,6],[4,7],[4,4],[2,5],[1,1]], origin = [0, 0], k = 3
	// 返回 [[1,1],[2,5],[4,4]]
	public static void main(String[] args) {
		System.out.println(Arrays.toString(kClosest(createPointArray(new int[][]{{4,6},{4,7},{4,4},{2,5},{1,1}}),new Point(0,0),5)));
	}
	
	private static Point[] createPointArray(int[][] nums) {
		Point[] points=new Point[nums.length];
		for(int i=0;i<nums.length;i++) {
			Point p=new Point();
			p.x=nums[i][0];
			p.y=nums[i][1];
			points[i]=p;
		}
		return points;
	}

	public static Point[] kClosest(Point[] points, Point origin, int k) {
		if(k>points.length)k=points.length;
		Arrays.sort(points,new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				long x1=o1.x-origin.x;
				long y1=o1.y-origin.y;
				long x2=o2.x-origin.x;
				long y2=o2.y-origin.y;
				if(x1*x1+y1*y1>x2*x2+y2*y2) {
					return 1;
				}else if(x1*x1+y1*y1<x2*x2+y2*y2) {
					return -1;
				}else {
					if(x1>x2) {
						return 1;
					}else if(x1<x2) {
						return -1;
					}else {
						if(y1>y2) {
							return 1;
						}else if(y1<y2) {
							return -1;
						}else return 0;
					}
				}
			}
		});
		return Arrays.copyOf(points, k);
	}
	
	

	public static class Point {
		int x;
		int y;

		public Point() {
			x = 0;
			y = 0;
		}

		public Point(int a, int b) {
			x = a;
			y = b;
		}

		@Override
		public String toString() {
			return "{\"x\":\"" + x + "\",\"y\":\"" + y + "\"} ";
		}
	}
}
